﻿//斐波那契数(easy): https://leetcode.cn/problems/fibonacci-number/description/
class Solution {
public:
    int memo[35];
    int fib(int n) {
        memset(memo,-1,sizeof(memo));
        return dfs(n);
    }
    int dfs(int n)
    {
        if(memo[n]!=-1)
        {
            return memo[n];
        }
        if(n==0||n==1)
        {
            memo[n]=n;
            return n;
        }
        return dfs(n-1)+dfs(n-2);
    }
};
//不同路径(medium): https://leetcode.cn/problems/unique-paths/description/
class Solution {
public:
    int m,n;
    int ret;
    int memo[110][110];
    int uniquePaths(int _m, int _n) {
        m=_m,n=_n;
        return dfs(m,n);;
    }
    int dfs(int i,int j)
    {
        if(i==0||j==0)  return 0;
        if(i==1&&j==1)  return 1;
        
        if(memo[i][j])
        {
            return memo[i][j];
        }
       
        memo[i][j]=dfs(i,j-1)+dfs(i-1,j);
        return memo[i][j];
    }
};